Searching a Graph Depth-First
In this article we shall speak about Depth First Search algorithm and how to use it to solve problems. DFS is one of the most basic algorithms: many other algorithms use it and to tell the truth, DFS is a foundation of all these algorithms. The most common using of DFS is traversal of graph. Often it is used for determining whether a graph is acyclic, topsort, searching components.
The main strategy of this algorithm (as it can be seen from its name) is going in depth while it is possible. I think that it is easier to understand recursive implementation of DFS, so here it is. Imagine that DFS–function is called from vertex v. What do we do is just go through all its neighbors, which we haven’t visited, and call DFS from each of them recurrently one after another. For example, if vertices are people and relations between vertices are father-son relations between people: let’s imagine that DFS is called from my grandfather. We call DFS from his first son (my father) then, we do the same with my father and call DFS from me. As I don’t have children, we do a step back to my father and call DFS from his second son (my brother). As you can see we went down from grandfather to me – to the depth. And if we can’t go deeper, we go one step back (using return from function).
Pseudocode for answering if is a path between vertices a and b exists is like this:
boolean visited[N];
1 2 3 4 5 6 7 8 9 10
boolean DFS(vertex a, vertex b) { if (a == b) return true; if (visited[a]) return false; visited[a] = true; for (vertex c adjacent to a) if (DFS(c)) return true; return false; }
To do the same, but not recursively, e.g. faster implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
boolean DFS(vertex a, vertex b) { boolean visited[N]; stack < vertex > s; s.push(a); visited[a] = true; while (s is not empty) { vertex top = s.top(); s.pop(); if (top == b) return true; for (vertex c adjacent to top) { if (visited[c] == false) { s.push(c); visited[c] = true; } } } return false; }
Anyway, main thing this algorithm is used for is traversal of graph. And if we want to be in every vertex just once, we should use something to mark vertices we visited, not to go there once more, here we use array visited. When we visit a vertex a, we mark it: visited[a] = true.
If we want to find graph components, we need to go through vertices and if current vertex is not visited we call dfs from it. dfs goes through (visits) all vertices reachable from the current and adds them to the current component. Our pseudocode should look like this (N – number of vertices):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
component comp;
boolean visited[N];
void dfs(vertex a) {
if (visited[a]) return;
visited[a] = true;
comp.add(a);
for (vertex c adjacent to a)
DFS(c);
return;
}
int main() {
for (int i = 0; i < N; i++) {
if (!visited[i]) {
comp.clear();
DFS(i);
comp.print();
}
}
return 0;
}